CSCI 0026. Discrete Structures for Computer Science
Units: 3
Prerequisite: Completion of CSCI 12 and MATH 12 with grades of "C" or better
Hours: 72 (54 lecture, 18 laboratory)
Introduction to the essential discrete structures used in Computer Science, with emphasis on their applications. Includes elementary formal logic and set theory, elementary combinatorics, recursive programming and algorithm analysis, Boolean algebra, digital logic, combinatorial circuits, graph theory, circuit design and minimization, and computer arithmetic. (C-ID COMP 152) (CSU, UC)
CSCI 0026 - Discrete Structures for Computer Science
http://catalog.sierracollege.edu/course-outlines/csci-0026/
Catalog Description DESCRIPTION IS HERE: Prerequisite: Completion of CSCI 12 and MATH 12 with grades of "C" or better Hours: 72 (54 lecture, 18 laboratory) Description: Introduction to the essential discrete structures used in Computer Science, with emphasis on their applications. Includes elementary formal logic and set theory, elementary combinatorics, recursive programming and algorithm analysis, Boolean algebra, digital logic, combinatorial circuits, graph theory, circuit design and minimization, and computer arithmetic. (C-ID COMP 152) (CSU, UC) Units 3 Lecture-Discussion 54 Laboratory 18 By Arrangement Contact Hours 72 Outside of Class Hours Course Student Learning Outcomes Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms. Relate the ideas of mathematical induction to recursion and recursively defined structures. Analyze a problem to create relevant recurrence equations. Demonstrate different traversal methods for trees and graphs. Apply the binomial theorem to independent events and Bayes’ theorem to dependent events. Course Content Outline I. Survey of Number Systems A. Binary representation of integers and floating-point numbers B. Octal, decimal, and hexadecimal representations of integers C. Binary arithmetic D. Modular arithmetic E. Basic arithmetic algorithms F. Modular arithmetic G. Data compression, encoding, and encryption II. Sets and Relations A. Sets, sequences and strings B. Relations C. Functions III. Logic and Proofs A. Propositions B. Conditional propositions and logical equivalence C. Quantifiers D. Proofs E. Mathematical induction IV. Counting Methods A. Basic principles B. Permutations C. Combinations D. The pigeonhole principle E. Binomial theorem F. Discrete probability with Bayes' Theorem V. Recursive Programs A. Well-structured recursive functions B. Recursive procedures C. Implementation and efficiency of recursive algorithms D. Examples including several sort and search techniques E. Introduction to analysis and complexity of algorithms (Big-O) VI. Digital Logic A. Boolean algebra B. Introduction to logic gates C. The universal NAND and NOR gates VII. Implementation of Logic Gates A. Combinational circuits B. Circuit design methodology C. Circuit minimization D. Switches and transistors E. Full and half adders VIII. Graph Theory A. Minimum spanning tree B. Breadth-first and depth-first traversals C. Shortest path IX. Basic Models of Computation A. Languages and grammars B. Finite-state machines C. Regular expressions D. Parsers Course Objectives Course Objectives Lecture Objectives: 1. Convert between decimal, hexadecimal and binary representation of numbers. 2. Convert negative decimal numbers to two's complement binary form. 3. Analyze sets for complement, union and intersection. 4. Construct Venn diagrams to illustrate set relationships and operations. 5. Evaluate sets for reflexivity, symmetry, and transitivity. 6. Encrypt and decrypt a string of text using the RSA algorithm and modular arithmetic. 7. Identify problems appropriately solved with recursive functions. 8. Convert floating point notation (IEEE-754) to decimal and binary. 9. Recognize digital logic gates and their representation in graphical, algebraic, and truth table form. 10. Convert Boolean functions between algebraic expressions, truth tables and circuit diagrams. 11. Convert an English-language statement of compound propositions (including and, or, not, and quantifiers) to a symbolic form. 12. Identify and solve combinatorial word problems using permutations, combinations, pigeonhole principle, inclusion/exclusion principle, and/or product rule. 13. Compute discrete probabilities of conditional events using Bayes' Theorem. 14. Compare and contrast the "Big-O" running time of common searching and sorting algorithms. 15. Minimize circuits and Boolean expressions by creating Karnaugh Maps. 16. Analyze a graph for the shortest path between two vertices and the minimal spanning tree. 17. Create regular expressions for sets of strings. 18. Create a finite-state automaton from a written description of a set of strings. Laboratory Objectives: 1. Design and construct logic circuits using AND, OR, NOT, NAND, and/or XOR gates from written descriptions. 2. Analyze inputs and outputs for the creation of functions that manipulate numbers, strings, lists, sets, and tuples; 3. Write and test recursive functions on numbers, lists, strings, sets, and tuples; 4. Analyze strings to derive appropriate regular expressions and test them against a corpus of text; 5. Analyze a regular language and construct a regular expression for it; and 6. Write and test functions to encrypt and decrypt strings using shift, linear, and RSA ciphers. Methods of Evaluation Classroom Discussions Problem Solving Examinations Projects Reading Assignments 1. Read the section in the textbook on modular arithmetic to learn how to compute the multiplicative inverse. Be prepared to discuss in class. 2. Read the Wikipedia article on the RSA encryption system to learn who invented it, the underlying computations used, and its strengths and weaknesses. Be prepared to discuss in class. Writing, Problem Solving or Performance 1. Using the "repeated division" method, convert the decimal number 29 to binary and hexadecimal. Answer: 29 / 2 = 14 r 1; 14 / 2 = 7 r 0; 7 / 2 = 3 r 1; 3 / 2 = 1 r 1; 1 / 2 = 0 r 1. The solution can be read in the remainders from right to left: 11101. Hexadecimal follows from the binary solution by partitioning into groups of 4 and converting each group to hexadecimal: 1 | 1101 -> 1D 2. Compute at least three strings recognized by this regular expression: b(c|d)*b Sample answers: bb, bcb, bdb, bcccd, bcdcd, bcdcccdb Other (Term projects, research papers, portfolios, etc.) Methods of Instruction Laboratory Lecture/Discussion Distance Learning Other materials and-or supplies required of students that contribute to the cost of the course.
Course Identification Numbering System (C-ID)
...122 CSCI 0012 COMP 132 CSCI 0013 COMP 142 CSCI 0039 COMP 152 CSCI 0026...
